#include "kasiski.h"
#include <limits.h>

static void addElem(int * array, int *size, int elem);


void
colCesar(int* s, long size, alphabetArray cypherFreq, int i)
{
   letterStat maxCypher;
   int rotation;
  
   maxCypher = getMaxFreq (cypherFreq);

   rotation = maxCypher.c - sortedSpanishFrequencies[i].c;

   if (rotation < 0)
	   rotation = ALPHABET_NUM - sortedSpanishFrequencies[i].c + maxCypher.c;
 
   unRotate(s, size, rotation);
}

int *
findKeyLength(int * s, int size)
{
	int * keyLengths, i, j, k, numDist = 0;
	int textLength = size;
	strDist * distances, * aux;
	int * substr, * strPos;

	if ( (distances = malloc(sizeof(strDist) * NUM_ITEMS)) == NULL )
	   return NULL;
	   
	if ( (substr = malloc(sizeof(int) * (MAX_KEY_LENGTH) )) == NULL )
	   return NULL;

	for (j = MAX_KEY_LENGTH; j >= SEQ_LENGTH; j--)
	{

		for (i = 0; i < textLength - j + 1; i++)
		{
			memcpy(substr, &s[i], j*sizeof(int));
			strPos = &s[i];
			
			for (k = j; k < textLength - i - j; k++)
			{
				if ( memcmp(substr, &strPos[k], j*sizeof(int)) == 0)
				{
					distances[numDist].dist = k;
					distances[numDist].seqLength = j;
					
//		printf("long: %d, dist: %d\n", distances[numDist].seqLength, distances[numDist].dist);
					numDist++;
					
					if (numDist % NUM_ITEMS == 0)
					{
						aux = distances;
						if ( (distances = realloc(distances, sizeof(strDist) * (numDist + NUM_ITEMS))) == NULL )
						{
							free(aux);
							return NULL;
						}
					}
				
				}
			}
		}
	}

	keyLengths = calcKeyLength(distances, numDist);
	
	free(distances);
	free(substr);

	return keyLengths;
}

int *
calcKeyLength(strDist * distances, int numDist)
{
	int i, maxDiv, aux, idx = 0;
	int * keys;
	
	if ( (keys = malloc(sizeof(int)*(MAX_KEY_LENGTH + 1))) == NULL)
	   return NULL;

	if (numDist < 1)
		return NULL;
	if (numDist == 1)
	{
	   keys[0] = distances[0].dist;
      keys[1] = -1;
		return keys;
   }

	maxDiv = maxDivisor(distances[0].dist, distances[1].dist);
	if (maxDiv <= 1)
	{
		maxDiv = distances[0].dist;
	   if (maxDiv <= MAX_KEY_LENGTH)
	      addElem(keys, &idx, maxDiv);
   }
	for (i = 2; i < numDist; i++)
	{
		aux = maxDivisor(maxDiv, distances[i].dist);
		if (aux > 1)
		{
			maxDiv = aux;
			if (maxDiv <= MAX_KEY_LENGTH)
   	      addElem(keys, &idx, maxDiv);
   		}
	}

   //saco divisores de la mejor clave
   for (i = 2; i <= keys[0] /2; i++)
	   	if ( (keys[0] % i) == 0)
	   		addElem(keys, &idx, i);
   		
   keys[idx] = -1;

	return keys;
}

int
maxDivisor(int n1, int n2)
{
	if (n1 < n2)
		return maxDivisor(n2, n1);
		
	if (n2 == 0)
		return n1;
	
	return maxDivisor(n2, n1 % n2);
}

vigColum *
allocColumns(int textSize, int keyLength)
{
	int i, aux;
	vigColum * columns;
	
	if ( (columns = malloc(sizeof(vigColum) * (keyLength) )) == NULL )
	   return NULL;
	
	for (i = 0; i < keyLength; i++)
	{
		aux = ( ((textSize % keyLength) / (i + 1)) != 0 )? 1:0;
		columns[i].size = textSize / keyLength + aux;
		
		if ( (columns[i].col = malloc(sizeof(int) * (columns[i].size) )) == NULL )
			return NULL;
	}
	
	return columns;
}

void
freeColumns(vigColum * columns, int length)
{
	int i;
	
	for (i = 0; i < length; i++)
		free(columns[i].col);
	
	free(columns);
	
	return;
}

void
solveVigenere(int * s, int size)
{
	int keyLength, * keyLengths, i, j, k, count;
	vigColum * columns, * aux;
	alphabetArray cypherFreq[10];
	char v[MAX_KEY_LENGTH] = {0,0,0,0,0,0,0,0,0,0};	//me dice cuantas veces probe cesar
	char check[MAX_KEY_LENGTH] = {1,1,1,1,1,1,1,1,1,1};	//me dice si debo chequear cesar
	char flag;
	float indexCoin, minDiff = INT_MAX;
	
	keyLengths = findKeyLength(s, size);
	
	if (keyLengths[0] < 0)
	{
		printf("Error en vigenere\n");
		return;
	}
	
	i = 0;
	while (keyLengths[i] > 0)
	{
   	if ( (columns = makeColumns(size, s, keyLengths[i])) == NULL)
	      return;
	   
	   indexCoin = 0;
	   for (j = 0; j < keyLengths[i]; j++)
      {   
	      computeFrequencies(columns[j].col, columns[j].size, &(cypherFreq[j]) );
	      indexCoin += computeIndexOfCoincidence (cypherFreq[j], columns[j].size);
      }
      indexCoin = indexCoin / j;

      if (abs(indexCoin-spanishIC) < minDiff)
      {
         minDiff = abs(indexCoin-spanishIC);
         keyLength = j;
      }
      
		freeColumns(columns, keyLengths[i]);
		i++;
	}

	printf("Longitud de clave: %d\n", keyLength);

	if ( (aux = allocColumns(size, keyLength) ) == NULL )
	{
		printf("Error en vigenere\n");
		freeColumns(columns, keyLength);
		return;
	}
	
	if ( (columns = makeColumns(size, s, keyLength)) == NULL)
	      return;
	
	for (i = 0; i < keyLength; i++)
	{   
		computeFrequencies(columns[i].col, columns[i].size, &(cypherFreq[i]) );
	}
	
	//ofrece varias posibles soluciones
	for (j = 0; j < NUM_RESP; j++)
	{
		for (i = 0; i < keyLength; i++)
		{   
			if (check[i] != 0)
			{
				memcpy(aux[i].col, columns[i].col, aux[i].size * sizeof(int));
				colCesar(aux[i].col, aux[i].size, cypherFreq[i], v[i]);
			}
		}
		
		//armo el texto que voy a mostrar
		for (i = 0; i < size; i++)
		{
			s[i] = aux[i % keyLength].col[i/keyLength];
		}
		
		printf("Opcion %d\n", j);
		printIntArray(s, size);
		printf("\n\n");
		
		flag = 0;
		//chequeo si hay alguna columna candidata a ser cambiada con otro cesar
		for (i = 0; i < keyLength; i++)
		{
			count = 0;
			if (check[i] != 0)
			{
				for (k = 0; k < aux[i].size; k++)
				{
					//Esto es lo que dispara la decision de rehacer cesar.
					if (aux[i].col[k] == LETRA_W || aux[i].col[k] == LETRA_X 
						 || aux[i].col[k] == LETRA_ENIE || aux[i].col[k] == LETRA_K)
					{
						count++;
						if (count >= 3)
						{
							v[i]++;
							flag = 1;
							break;
						}
					}
				}
				
				if (count >= 3)
					check[i] = 1;
				else
					check[i] = 0;
			}
		}
		if (!flag) //si no cambio nada mas, salgo y no ofrezco mas soluciones
			break;
	}

	freeColumns(columns, keyLength);
	freeColumns(aux, keyLength);
	free(keyLengths);
	
	return;	
}


vigColum *
makeColumns(int size, int * s, int keyLength)
{
   int i;
   vigColum * columns;

  	if ( (columns = allocColumns(size, keyLength) ) == NULL )
	{
		printf("Error in vigenere\n");
		return NULL;
	}

	//separo en columnas
	for (i = 0; i < size; i++)
	{
		columns[i % keyLength].col[i/keyLength] = s[i];
	}
	
	return columns;	
}

static void
addElem(int * array, int *size, int elem)
{
   int i;
   
   if (size == NULL || *size < 0)
      return;
   
   for (i = 0; i < *size; i++)
      if (elem == array[i])
         return;
   
   array[*size] = elem;
   (*size)++;
   
   return;
}
